PEG Parsers (by Guido van Rossum)
the home-grown parser generator that I developed 30 years ago when I started working on Python. (That parser generator, dubbed “pgen”, was just about the first piece of code I wrote for Python.)
Guido氏が書いたかつてのパーサジェネレータはpgenと呼ばれる
EBNF parserのannoyance(悩みのタネ)
The “1” in the LL(1) moniker implies that it uses only a single token lookahead, and this limits our ability of writing nice grammar rules.
「LL(1)の1は単一のトークンだけを先読みに使えることを示す」
「これはすてきな文法規則が書ける私達の能力を制限する」
One of the issues is that some rules (expr and term) are left-recursive, and pgen isn’t smart enough to do the right thing here.
「いくつかの規則は左再帰だが、pgenは正しいことができるほど賢くない」
ワークしない:expr: expr '+' term | expr '-' term | term
このように変える必要あり:expr: term ('+' term | '-' term)*
Because of the single-token lookahead, the parser cannot determine whether it is looking at the start of an expression or an assignment.
規則:statement: assignment | expr | if_statement
例:answer = 42
3つのトークンに分かれる
NAME (with value answer), '=', and NUMBER (with value 42).
'if'トークンで始まらないので、if_statementではない
But both expr and assignment (can) start with a NAME token, and because of this pgen rejects our grammar as being ambiguous.
toy exampleでは先読み2語で解決するが、実際のプログラムでは'='の前に10個のトークンが現れるような場合もある
What we’ve done to solve this in pgen is to change the grammar to accept some illegal programs, adding an extra check in a later pass that generates a SyntaxError if it finds an invalid left-hand side for an assignment.
「pgenで解決するために、文法を不正なプログラムを受理するように変えた」
「さらに、代入について不正な左辺を見つけたときにSyntaxErrorを生成する追加の後出し(?)チェックを加えた」
(in a later passが後出し的な意味? ここだけ意味が取りづらかったが、DeepLがそう返した)
code:解決法の例
statement: assignment_or_expr | if_statement
assignment_or_exprという規則を作った
But the single-token lookahead can’t to tell the parser whether a NAME at the start of an argument is the beginning of posarg (since expr may start with NAME) or the beginning of kwarg.
arg: posarg | kwarg
「単一のトークンの先読みでは、実引数の始まりのNAMEがposargの始まりかkwargの始まりか判断できない」
解決法:arg: expr ['=' expr]
Python 3.8で修正するまではfoo(a=1)と同じ意味のfoo((a)=1)ができた
(感想:EBNFがなぜあのようになっているかがわかる)
So how does a PEG parser solve these annoyances? By using an infinite lookahead buffer!
「無限の先読みバッファ」
packrat parsing
not only loads the entire program in memory before parsing it, but also allows the parser to backtrack arbitrarily.
「プログラムをパースする前に全体をメモリに読み込むだけでなく、パーサが任意に引き返すことを可能にもする」
While the term PEG primarily refers to the grammar notation, the parsers generated from PEG grammars are typically recursive-descent parsers with unlimited backtracking
「PEGという語は主として文法記法を呼ぶが、PEG文法から生成されたパーサ(構文解析器)は一般に、制限のないバックトラックができる再帰下降パーサである」
and packrat parsing makes this efficient by memoizing the rules already matched for each position.
「packrat parsingは各位置ですでにマッチした規則をメモすることでこれ(制限のないバックトラックができる再帰下降パーサ)を効率的にする」
Guido氏がパーサを書いた30年前と比べて、メモリが高価でなくなったのでPEGパーサが実現できるようになった(と理解)
Fortunately the computers on which CPython runs have a lot more memory than 30 years ago,
But there’s another thing about CPython’s current parser that bugs me.
this parse tree is not directly used as the input to the code generator: first it is transformed to an abstract syntax tree (AST), and then that AST is compiled into bytecode
「pgenで生成したパーサによる構文解析木はASTにまず変換され、それからASTがバイトコードにコンパイルされる」
create a new parser for CPython that uses PEG and packrat parsing to construct the AST directly during parsing
「新しいパーサは構文解析の間に直接ASTを構築する」
A final advantage of switching to PEG is that it provides more flexibility for future evolution of the language.